package madixin.t785;

import java.util.Arrays;

class Solution {
    public boolean isBipartite(int[][] graph) {
        if (graph == null || graph.length <= 0) {
            return false;
        }
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);
        for (int i = 0; i < color.length; i++) {
            if (color[i] == -1) {
                if (!DFS(graph, color, i, 1)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean DFS(int[][] graph, int[] color, int curNode, int curColor) {
        if (color[curNode] != -1) {
            return color[curNode] == curColor;
        }
        color[curNode] = curColor;
        for (int i = 0; i < graph[curNode].length; i++) {
            if (!DFS(graph, color, graph[curNode][i], 1 - curColor)) {
                return false;
            }
        }
        return true;
    }


    //https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%9B%BE.md#1-%E8%AF%BE%E7%A8%8B%E5%AE%89%E6%8E%92%E7%9A%84%E5%90%88%E6%B3%95%E6%80%A7
    //二分图：如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么这个图就是二分图。
    public boolean isBipartite1(int[][] graph) {
        if (graph == null || graph.length <= 0) {
            return false;
        }
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);
        for (int i = 0; i < color.length; i++) {
            if (color[i] == -1 && !fillColor(graph, color, i, 0)) {
                return false;
            }
        }
        return true;
    }

    private boolean fillColor(int[][] graph, int[] color, int curNode, int curColor) {
        System.out.println("fill" + curNode + "color" + curColor);
        if (color[curNode] != -1) {
            return color[curNode] == curColor;
        }
        color[curNode] = curColor;
        for (int nextNode : graph[curNode]) {
            if (!fillColor(graph, color, nextNode, 1 - curColor)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isBipartite(new int[][]{{1, 3}, {0, 2}, {1, 3}, {0, 2}}));
        System.out.println(s.isBipartite(new int[][]{{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}}));
    }
}